\chapter{Вопрос №6}

Подсчет количества разделений и упорядоченных разбиений множества $X$. Перестановки с повторениями. Биекции между количеством перестановок с повторениями и $k$-сочетниями без повторений и с повторениями.

\section{Количество разделений}

Система $S_X$ подмножеств множества $X$, покрывающая множество $X$, называется разбиением множества $X$, если различные подмножества из семейства не пересекаются, и ни одно из них не является пустым.

Упорядоченное разбиение, в котором допустимы пустые подмножества, называется разделением.

Задача о поиске всех $k$-разделений эквивалентна задаче о раскладке $n$ различных предметов по $k$ различным ящикам. В терминах отображений, каждое отображение из $n$-множесва в $k$-множество - разделение исходного $n$-множества, откуда число радзделений равно $$ k^n $$

\section{Перестановки с повторениями}

Пусть имеется $n$-множество $X$, рассмотрим его $k$-разбиения, причем такие, что число элементов в $i$-ом блоке разбиения равно $a_i$. Понятно, что  $$ \sum_{i=1}^k a_i = n $$

Каково же количество таких разбиений, если порядок внутри блока разбиения значения не имеет? Количество спосбов сформировать первый блок очевидно равно $\binom{n}{a_1}$, после этого из оставшихся элементов сформировать второй блок возможно $\binom{n-a_1}{a_2}$ способами и так далее, пока не сформируем все блоки:
\begin{equation}
	P\left(n;a_1,...,a_k\right) = \prod_{i=1}^k \binom{n - \sum_{t=1}^{i-1} a_t}{a_i}
\end{equation}
Используя явную формлу
\begin{equation}
	\binom{n}{k} = \frac{n!}{k!\left(n-k\right)!}
\end{equation}
можно полуить следующую формулу:
\begin{equation}
	P\left(n;a_1,...,a_k\right) = \frac{n!}{a_1!a_2!...a_k!}
\end{equation}
Эти числа называются перестановками множества $X$ с повторениями, почему перестановки покажем на следующем примере. Пусть имеется 15 книг по математике, 16 книг по информатике и 12 книг по физике, сколькими способами можно расставить эти книги на полке, если считать, что книги по одному предмету не различимы? Ответ: $$ P\left(43; 15,16,12 \right) $$

\section{Биекции}

\begin{enumerate}
\item Очевидно, что: $$ P\left(n; k, n-k\right) = \frac{n!}{k!\left(n-k\right)!} = \binom{n}{k}$$ Если смотреть комбинаторно, то сущесвтует биекция между всеми строками длинны $n$ над алфавитом $\left\{1, 0\right\}$, в которой количество $1$ равно $k$, а количество $0$ равно $n-k$.

\item Пусть теперь у нас есть $k$ неразличимых предметов, добавим к ним еще $n-1$ предмет-перегородку. Тогда любая перестановка этих $k+n-1$ элементов эквивалентна некоторому разложению $k$ предметов по $n$ ящикам (с повторениями) и равно с одной стороны: $$ \Binomrep{n}{k} $$ а с другой стороны: $$ P\left(n+k-1; n-1, k\right) = \binom{n+k-1}{k} $$
\end{enumerate}
